//class Solution {
//public:
//    int n = 0, m = 0;
//    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
//        n = nums1.size();
//        m = nums2.size();
//        if ((n + m) % 2 == 0) {
//
//            return ((double)fun(nums1, nums2, (n + m) / 2) + fun(nums1, nums2, (n + m) / 2 + 1)) 
//                /2;
//        }
//        else {
//            return fun(nums1, nums2, (n + m + 1) / 2);
//        }
//    }
//    int fun(vector<int>& nums1, vector<int>& nums2, int x) {
//        int begin1 = 0, begin2 = 0;
//        int data1 = nums1[begin1], data2 = nums2[begin2];
//        while (x != 1) {
//            x--;
//            if (begin1 != n && data1 <= data2) {
//                begin1++;
//                data1 = begin1 == n ? INT_MAX : nums1[begin1];
//            }
//            else if (begin2 != m && data1 >= data2) {
//                begin2++;
//                data2 = begin2 == m ? INT_MAX : nums2[begin2];
//            }
//            else {
//                printf("abcdef");
//                return 0;
//            }
//        }
//        return min(data1, data2);
//    }
//};
//class Solution {
//public:
//    int n = 0, m = 0;
//    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
//        n = nums1.size();
//        m = nums2.size();
//        if ((n + m) % 2 == 0) {
//            return ((double)fun(nums1, nums2, (n + m) / 2) +
//                fun(nums1, nums2, (n + m) / 2 + 1)) /
//                2;
//        }
//        else {
//            return fun(nums1, nums2, (n + m + 1) / 2);
//        }
//    }
//    int fun(vector<int>& nums1, vector<int>& nums2, int x) {
//        int begin1 = 0, begin2 = 0;
//        int len = max(x / 2 - 1,0);
//        int data1 = (n <= begin1 + len) ? INT_MAX : nums1[begin1 + len];
//        int data2 = (m <= begin2 + len) ? INT_MAX : nums2[begin2 + len];
//        while (x != 1) {
//            len = max(min(x / 2 - 1, min(n - begin1, m - begin2) - 1),0);
//            x -= (len + 1);
//            data1 = (begin1+len) >= n ? INT_MAX : nums1[begin1 + len];
//            data2 = (begin2+len) >= m ? INT_MAX : nums2[begin2 + len];
//            if (data1 <= data2) {
//                begin1 += (len + 1);
//                if (begin1 == n) return nums2[begin2 + x - 1];
//                data1 = nums1[begin1];
//            }
//            else if (data1 >= data2) {
//                begin2 += (len + 1);
//                if (begin2 == m) return nums1[begin1 + x - 1];
//                data2 = nums2[begin2];
//                //data2 = begin2 >= m ? INT_MAX : nums2[begin2];
//            }
//        }
//        return min(data1, data2);
//    }
////};
//class Solution {
//public:
//    int n = 0, m = 0;
//    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
//        n = nums1.size();
//        m = nums2.size();
//        if ((n + m) % 2 == 0) {
//            return ((double)fun(nums1, nums2, (n + m) / 2) +
//                fun(nums1, nums2, (n + m) / 2 + 1)) /
//                2;
//        }
//        else {
//            return fun(nums1, nums2, (n + m + 1) / 2);
//        }
//    }
//    int fun(vector<int>& nums1, vector<int>& nums2, int x) {
//        if (n == 0)  return nums2[x - 1];
//        if (m == 0)  return nums1[x - 1];
//        int begin1 = 0, begin2 = 0;
//        int len = x / 2;
//        int data1 = nums1[0]; // = (n <= begin1 + len - 1) ? INT_MAX : nums1[begin1 + len - 1];
//        int data2 = nums2[0];//= (m <= begin2 + len - 1) ? INT_MAX : nums2[begin2 + len - 1];
//
//        while (x != 1) {
//            len = min(x / 2, min(n - begin1, m - begin2));
//            x -= (len);
//            data1 = (begin1 + len - 1) >= n ? INT_MAX : nums1[begin1 + len - 1];
//            data2 = (begin2 + len - 1) >= m ? INT_MAX : nums2[begin2 + len - 1];
//            if (data1 <= data2) {
//                begin1 += (len);
//                if (begin1 == n)
//                    return nums2[begin2 + x - 1];
//                data1 = nums1[begin1];
//            }
//            else if (data1 >= data2) {
//                begin2 += (len);
//                if (begin2 == m)
//                    return nums1[begin1 + x - 1];
//                data2 = nums2[begin2];
//            }
//        }
//        return min(data1, data2);
//    }
//};
//class Solution {
//public:
//    int n = 0, m = 0;
//    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
//        int left = 0, right = nums1.size();
//        n = nums1.size(), m = nums2.size();
//        int size = nums1.size() + nums2.size();
//        int rembermin = 0, rembermax = 0;
//        while (left <= right) {
//            int i = (left + right) / 2;
//            int j = (size + 1) / 2 - i;
//            int data1_left = i == 0 ? INT_MIN : nums1[i - 1];
//            int data1_right = i == n ? INT_MAX : nums1[i];
//            int data2_left = j == 0 ? INT_MIN : nums1[j - 1];
//            int data2_right = j == m ? INT_MAX : nums1[j];
//            if (data1_left > data2_right) {
//                right = i - 1;
//                rembermax = max(data1_right, data2_right);
//                rembermin = min(data1_left, data2_left);
//            }
//            else {
//                left = i + 1;
//            }
//        }
//        return (m + n) % 2 == 0 ? (rembermax + rembermin) / 2.0 : rembermax;
//    }
//
//};
class Solution {
public:
    int n = 0, m = 0;
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        if (nums1.size() > nums2.size()) {
            return findMedianSortedArrays(nums2, nums1);
        }
        int left = 0, right = nums1.size();
        m = nums1.size(), n = nums2.size();
        // int size = nums1.size() + nums2.size();
        int rembermin = 0, rembermax = 0;
        while (left <= right) {
            int i = (left + right) / 2;
            int j = (m + n + 1) / 2 - i;
            int data1_left = i == 0 ? INT_MIN : nums1[i - 1];
            int data1_right = i == m ? INT_MAX : nums1[i];
            int data2_left = j == 0 ? INT_MIN : nums1[j - 1];
            int data2_right = j == n ? INT_MAX : nums1[j];
            if (data1_left <= data2_right) {
                left = i + 1;
                rembermax = min(data1_right, data2_right);
                rembermin = max(data1_left, data2_left);
            }
            else {
                right = i - 1;
            }
        }
        return (m + n) % 2 == 0 ? (rembermax + rembermin) / 2.0 : rembermin;
    }

};

int main()
{
    vector<int> v1 = {1,3};
    vector<int> v2 = {2,4};
    Solution().findMedianSortedArrays(v1,v2);
}
